package projectg06.grafosmm;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.ObjectInputStream.GetField;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Random;
import static java.lang.System.out;

public class Grafo {
	private static final Random random = new Random();
	public static final String PATH = ".\\test\\";
	public static final String PACK = "cromatico\\";
	public static final String IN = "input\\";
	public static final String OUT = "output\\";

	private List<Nodo> universoDeNodos = new ArrayList<Nodo>();
	private int matrizAdy[][];

	public Grafo(int cantNodos) {
		this(cantNodos, false);
	}

	public Grafo(int cantNodos, boolean aleatorio) {

		matrizAdy = new int[cantNodos][cantNodos];

		for (int x = 0; x < cantNodos; x++) {
			universoDeNodos.add(new Nodo(x));
			for (int y = x + 1; y < cantNodos; y++) {
				if (aleatorio)
					matrizAdy[x][y] = random.nextInt(101) > 75 ? 0 : 1;
				else
					matrizAdy[x][y] = 0;
				matrizAdy[y][x] = matrizAdy[x][y];
			}
		}
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		for (int i = 0; i < matrizAdy.length; i++)
			result = prime * result + Arrays.hashCode(matrizAdy[i]);
		result = prime * result + ((universoDeNodos == null) ? 0 : universoDeNodos.hashCode());
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		Grafo other = (Grafo) obj;
		if (matrizAdy.length != other.matrizAdy.length)
			return false;
		for (int i = 0; i < matrizAdy.length; i++)
			if (!Arrays.equals(matrizAdy[i], other.matrizAdy[i]))
				return false;
		if (universoDeNodos == null) {
			if (other.universoDeNodos != null)
				return false;
		} else if (!universoDeNodos.equals(other.universoDeNodos))
			return false;
		return true;
	}

	@Override
	protected Object clone() {
		Grafo gr = new Grafo(universoDeNodos.size());
		gr.setMatrizAdy(matrizAdy);
		return gr;
	}

	@Override
	public String toString() {
		StringBuffer sb = new StringBuffer();
		Iterator<Nodo> it = universoDeNodos.iterator();
		Nodo nodoX;
		sb.append("X  ");
		while (it.hasNext())
			sb.append(it.next().id).append("  ");
		it = universoDeNodos.iterator();
		while (it.hasNext()) {
			nodoX = it.next();
			sb.append("\n").append(nodoX).append("  ");
			Iterator<Nodo> nodosY = universoDeNodos.iterator();
			while (nodosY.hasNext())
				sb.append(getCosto(nodoX, nodosY.next())).append("  ");
		}
		return sb.toString();
	}

	public String mostrarNodos() {
		StringBuffer sb = new StringBuffer();
		sb.append("id\tcolor\tgrado\r\n");
		for (Nodo n : universoDeNodos) {
			sb.append(n.id).append("\t").append(n.color).append("\t").append(n.grado).append("\r\n");
		}
		return sb.toString();
	}

	public int getCosto(Nodo nodoX, Nodo nodosY) {
		return matrizAdy[nodoX.id][nodosY.id];
	}

	public List<Arista> getAristas() {
		List<Arista> aristas = new ArrayList<Arista>();
		for (int i = 0; i < matrizAdy.length; i++) {
			for (int j = i; j < matrizAdy[i].length; j++) {
				if (matrizAdy[i][j] > 0)
					aristas.add(new Arista(i, j, matrizAdy[i][j]));
			}
		}
		return aristas;
	}

	private void relacionarNodos(Nodo nodoA, Nodo nodoB) {
		relacionarNodos(nodoA, nodoB, 1);
	}

	public void relacionarNodos(Nodo x, Nodo y, int costo) {
		if (!estanRelacionados(x, y)) {
			universoDeNodos.get(x.id).grado++;
			universoDeNodos.get(y.id).grado++;
		}
		matrizAdy[x.id][y.id] = costo;
		matrizAdy[y.id][x.id] = costo;
	}

	public void relacionarNodos(Arista arista) {
		relacionarNodos(arista.getNodoOrigen(), arista.getNodoDestino(), arista.getCosto());
	}

	public boolean estanRelacionados(Nodo x, Nodo y) {
		return matrizAdy[x.id][y.id] > 0;
	}

	public int getCantNodos() {
		return universoDeNodos.size();
	}

	public int[][] getMatrizAdy() {
		return matrizAdy;
	}

	public void setMatrizAdy(int[][] matrizAdy) {
		for (int i = 0; i < matrizAdy.length; i++)
			System.arraycopy(matrizAdy[i], 0, this.matrizAdy[i], 0, matrizAdy[i].length);
	}

	public List<Nodo> getUniversoNodos() {
		return new ArrayList<Nodo>(universoDeNodos);
	}

	public List<Nodo> getNodosConexos() {
		List<Nodo> conexos = new ArrayList<Nodo>();
		for (int i = 0; i < matrizAdy.length; i++) {
			for (int j = i; j < matrizAdy[i].length; j++) {
				if (matrizAdy[i][j] > 0) {
					conexos.add(new Nodo(i));
					conexos.add(new Nodo(j));
				}
			}
		}
		return conexos;
	}

	public List<Nodo> getNodosAdyacentes(Nodo origen) {
		List<Nodo> adyacentes = new ArrayList<Nodo>();
		for (Nodo nodo : universoDeNodos) {
			if (estanRelacionados(origen, nodo))
				adyacentes.add(nodo);
		}
		return adyacentes;
	}

	public List<Arista> getAristasIncidentes(Nodo origen) {
		List<Arista> aristas = new ArrayList<Arista>();
		for (Nodo nodo : universoDeNodos) {
			if (estanRelacionados(origen, nodo))
				aristas.add(new Arista(origen, nodo, getCosto(origen, nodo)));
		}
		return aristas;
	}

	// public boolean tieneCiclos(List<Nodo> arbol) {
	// List<Nodo> ramas;
	// boolean tieneCiclo = false;
	// List<Nodo> siguientes = getNodosAdyacentes(arbol.get(arbol.size() - 1));
	// for (Nodo sig : siguientes) {
	// ramas = new ArrayList<Nodo>(arbol);
	// if (ramas.size() > 1) {
	// if (ramas.subList(0, ramas.size() - 1).contains(sig))
	// return true;
	// } else
	// ramas.add(sig);
	// if (tieneCiclos(ramas))
	// return true;
	// }
	// return false;
	// }
	public void randomizeNodos() {
		for (Nodo n : universoDeNodos)
			n.actualizarRandom();
	}

	public boolean generaCiclos(Arista arista) {
		Grafo g = (Grafo) clone();
		g.colorearParticiones();
		Nodo origen = g.universoDeNodos.get(g.universoDeNodos.indexOf(arista.getNodoOrigen()));
		Nodo destino = g.universoDeNodos.get(g.universoDeNodos.indexOf(arista.getNodoDestino()));
		return origen.color == destino.color;
	}

	public static Grafo cargarGrafo(String filename) throws IOException{
		FileReader fr=new FileReader(PATH+IN+PACK+filename+".TXT");
		BufferedReader br=new BufferedReader(fr);
		String line=br.readLine();
		int n=Integer.parseInt(line);
		Grafo grafo=new Grafo(n);
		while((line=br.readLine())!=null&&!line.equals("")){
			String[] nodos=line.split(" ");
			int nodoOrigen=Integer.parseInt(nodos[0]);
			int nodoDestino=Integer.parseInt(nodos[1]);
			grafo.relacionarNodos(new Arista(nodoOrigen,nodoDestino));
		}
		br.close();
		return grafo;
	}
	
	public static void guardarGrafo(String filename, Grafo grafo) throws IOException{
		FileWriter fw=new FileWriter(PATH+OUT+PACK+filename+".TXT");
		BufferedWriter bw=new BufferedWriter(fw);
		bw.write(String.valueOf(grafo.getCantNodos()));
		List<Arista> aristas=grafo.getAristas();
		for(Arista ar:aristas){
			bw.write("\r\n"+ar.getNodoOrigen().id+" "+ar.getNodoDestino().id);
		}
		bw.close();
	}
	
	public void colorearParticiones() {
		List<Nodo> subUniv = getUniversoNodos();
		Nodo nodo;
		int i = 1;
		while (!subUniv.isEmpty()) {
			// Nueva particion
			List<Nodo> adyacentes = new ArrayList<Nodo>();
			nodo = subUniv.remove(0);
			nodo.color = i;
			adyacentes.add(nodo);
			adyacentes = getNodosAdyacentesSinColor(adyacentes);
			// out.println(mostrarNodos());
			while (!adyacentes.isEmpty()) {
				// coloreamos los nodos adyacentes sin color
				colorearNodos(adyacentes, i);
				// out.println(mostrarNodos());

				// eliminamos los nodos ya coloreados
				for (Nodo n : adyacentes) {
					subUniv.remove(n);
				}
				// tenga adyacentes y los adyacentes no estan en esta particion
				// **esta condicion se cumple porque se piden los no coloreados
				adyacentes = getNodosAdyacentesSinColor(adyacentes);
			}
			i++;
		}
	}

	/**
	 * 
	 * @param metodo
	 *            (MATULA|WELSH) o descendente (Welsh-Powell)
	 */
	private int aplicarColoreo(String metodo) {
		Comparator<Nodo> comp;
		if ("MATULA".equalsIgnoreCase(metodo))
			comp = new NodoCompMatula();
		else
			comp = new NodoCompWelshPowell();

		List<Nodo> subUniv = getUniversoNodos();
		List<Nodo> adyacentes;
		// ordenar los nodos por un random
		randomizeNodos();
		resetColor();
		Collections.sort(subUniv, new NodoComparator());
		Collections.sort(subUniv, comp);
		int i = 0;
		while (!subUniv.isEmpty()) {
			i++;
			Iterator<Nodo> it = subUniv.iterator();
			while (it.hasNext()) {
				Nodo nodo = it.next();
				adyacentes = getNodosAdyacentes(nodo);
				boolean sePuedeColorear = true;
				for (Nodo n : adyacentes) {
					if (n.color == i) {
						sePuedeColorear = false;
						break;
					}
				}
				if (sePuedeColorear) {
					nodo.color = i;
					it.remove();
				}
			}

		}
		return i;
	}

	private void resetColor() {
		for (Nodo nodo : universoDeNodos) {
			nodo.color = 0;
		}
	}

	private List<Nodo> getNodosAdyacentesSinColor(List<Nodo> adyacentes) {
		List<Nodo> adyacentesSinColor = new ArrayList<Nodo>();
		for (Nodo nodo : adyacentes) {
			adyacentesSinColor.addAll(getNodosAdyacentesSinColor(nodo));
		}
		return adyacentesSinColor;
	}

	private List<Nodo> getNodosAdyacentesSinColor(Nodo nodo) {
		List<Nodo> adyacentes = getNodosAdyacentes(nodo);
		Iterator<Nodo> it = adyacentes.iterator();
		while (it.hasNext()) {
			if (it.next().color != 0)
				it.remove();
		}
		return adyacentes;
	}

	private static void colorearNodos(List<Nodo> nodos, int i) {
		for (Nodo nodo : nodos) {
			nodo.color = i;
		}
	}



	private static void testearCromatico() {
		Grafo g = new Grafo(400, true);
		Map<Integer, Integer> resultados = new HashMap<Integer, Integer>();
		int cromatico;
		for (int i = 0; i < 500; i++) {
			cromatico = g.aplicarColoreo("");
			Integer hits = resultados.get(new Integer(cromatico));
			if (hits == null)
				hits = new Integer(0);
			resultados.put(new Integer(cromatico), new Integer(hits.intValue()+1));
		}
		out.println("Welsh-Powell");
		for(Map.Entry<Integer,Integer> entry:resultados.entrySet()){
			out.println(entry.getKey()+" "+entry.getValue());
		}
		for (int i = 0; i < 500; i++) {
			cromatico = g.aplicarColoreo("matula");
			Integer hits = resultados.get(new Integer(cromatico));
			if (hits == null)
				hits = new Integer(0);
			resultados.put(new Integer(cromatico), new Integer(hits.intValue()+1));
		}
		out.println("Matula");
		for(Map.Entry<Integer,Integer> entry:resultados.entrySet()){
			out.println(entry.getKey()+" "+entry.getValue());
		}
	}

	private static void test() {
		Grafo g = new Grafo(10,true);
		// for (int i = 0; i < 10; i++) {
		// Grafo aux = (Grafo) g.clone();
		// out.println(g.equals(aux));
		// }

		g.relacionarNodos(new Arista(0, 1, 5));
		g.relacionarNodos(new Arista(0, 4, 5));
		g.relacionarNodos(new Arista(1, 4, 5));
		g.relacionarNodos(new Arista(4, 7, 5));

		g.relacionarNodos(new Arista(2, 5, 5));
		g.relacionarNodos(new Arista(5, 8, 5));

		g.relacionarNodos(new Arista(3, 6, 5));
		g.relacionarNodos(new Arista(6, 9, 5));

		// g.relacionarNodos(new Nodo(0), new Nodo(6), 2);
		// g.relacionarNodos(new Nodo(0), new Nodo(1), 4);
		// g.relacionarNodos(new Nodo(3), new Nodo(4), 2);
		// g.relacionarNodos(new Nodo(3), new Nodo(6), 1);

		List<Nodo> recorridos = new ArrayList<Nodo>();
		recorridos.add(g.universoDeNodos.get(0));
		out.println(g);
		out.println(g.mostrarNodos());
		out.println(g.aplicarColoreo("matula"));
		out.println(g.mostrarNodos());

		// out.println(g.getNodosAdyacentes(new Nodo(5)));
		// g = new Grafo(8);
		// g.relacionarNodos(new Nodo(0), new Nodo(3), 5);
		// g.relacionarNodos(new Nodo(0), new Nodo(6), 2);
		// g.relacionarNodos(new Nodo(0), new Nodo(1), 4);
		// g.relacionarNodos(new Nodo(3), new Nodo(4), 2);
		// g.relacionarNodos(new Nodo(3), new Nodo(6), 1);
		// g.relacionarNodos(new Nodo(6), new Nodo(1), 1);
		// g.relacionarNodos(new Nodo(1), new Nodo(2), 5);
		// g.relacionarNodos(new Nodo(2), new Nodo(7), 1);
		// g.relacionarNodos(new Nodo(2), new Nodo(5), 1);
		// g.relacionarNodos(new Nodo(5), new Nodo(7), 2);
		// g.relacionarNodos(new Nodo(5), new Nodo(4), 1);
		// g.relacionarNodos(new Nodo(4), new Nodo(7), 3);
		// out.println(g);
	}
	
	public static void main(String[] args) throws IOException {
		// test();
		long ini=System.currentTimeMillis();
		testearCromatico();
		long fin=System.currentTimeMillis();
		long demora=fin-ini;
		out.println("Terminado en ["+(demora/(60*60*1000)%24)+":"+(demora/(60*1000)%60)+":"+(demora/(1000)%60)+","+(demora%1000)+"]");
		demora*=10;
		for(int i=100;i<100001;demora*=10,i*=10)
			out.println("Terminaria "+i+" en ["+(demora/(60*60*1000)%24)+":"+(demora/(60*1000)%60)+":"+(demora/(1000)%60)+","+(demora%1000)+"]");

		//testArchivos();
	}

	private static void testArchivos() throws IOException {
		Grafo g = new Grafo(5,true);
		out.println(g);
		guardarGrafo("001_Caso_de_prueba", g);
		out.println(cargarGrafo("001_Caso_de_prueba"));
	}
}
